#ifndef SOLUTION_H_
#define SOLUTION_H_
class Solution {
public:
    int climbStairs(int n) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
		int s[] = {0,1,2};
		if(n<=2)
			return s[n];

		for(int i=3;i<=n;i++){
			s[i%3] = s[(i-1)%3] + s[(i-2)%3];
		}

		return s[n%3];
    }
};
#endif